class MyCalendar {
    unordered_set<int> tree,lazy;
public:
    MyCalendar() {

    }
    
    bool query(int start,int end,int l,int r,int idx){
        if(r < start || l > end){
            return false;
        }
        if(lazy.count(idx)){
            return true;
        }
        if(l >= start && r <= end){
            return tree.count(idx);
        }
        int mid = (l + r) >> 1;
        return query(start,end,l,mid,idx * 2) ||
            query(start,end,mid + 1,r,idx * 2 + 1);
    }
    
    void update(int start,int end,int l,int r,int idx){
        if(start > r || end < l){
            return;
        }
        if(start <= l && end >= r){
            tree.insert(idx);
            lazy.insert(idx);
        }else{
            int mid = (l + r) >> 1;
            update(start,end,l,mid,idx * 2);
            update(start,end,mid+1,r,idx * 2 + 1);
            tree.insert(idx);
            if(lazy.count(2 * idx) && lazy.count(2 * idx + 1)){
                lazy.insert(idx);
            }
        }
    }
    
    bool book(int start, int end) {
        if(query(start,end - 1,0,1e9,1)){
            return false;
        }
        update(start,end - 1,0,1e9,1);
        return true;
    }
};
